package leetcode.editor.cn;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

//[239]滑动窗口最大值
public class SlidingWindowMaximum239{
public static void main(String[] args) {
   Solution solution = new SlidingWindowMaximum239().new Solution();
   
}

  //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
      //思路：
      //先进先出。addlast. poll.
      //cache list 左边最大值 ，is result ,
      //右边比左边大，左边就永无出头之日。
      // if (left < right ) poll
      // notify slidingWindow size int[] length
      public int[] maxSlidingWindow(int[] nums, int k)  {
          if (nums == null || nums.length <= 0 || k < 1)
              return new int[0];
          //当窗口 > 数组时，len = 1
          int[] result = new int[nums.length - k > 0 ? nums.length - k + 1 : 1];

          //存储 窗口数据的 index
          LinkedList<Integer> window = new LinkedList<Integer>();

          for (int j = 0; j < nums.length; j++) {
              //移除窗口缓存中的左边，窗口已经滑动过的元素
              if (window.size() >0 && window.peek()+k<=j)  {
                  window.poll();
              }

              //比较元素，移除左边元素，右边比左边大。（如果 左边<当前元素）
//              Iterator<Integer> iterator = window.iterator();
//              a:while (iterator.hasNext()) {//iterator 默认从队首遍历，
//                  Integer index = iterator.next();
//                  if (nums[index] <= nums[j]) {//左边<当前元素
//                      iterator.remove();
//                  }else {
//                      break a;//
//                  }
//              }
              //从队尾开始遍历
              // //迭代器遍历--反向输出 ,后边的数值小。如果遇到大的数，就可以停止了。
              ListIterator<Integer> iterator = window.listIterator(window.size());
              a:while (iterator.hasPrevious()) {// 从队尾开始遍历，
                  Integer index = iterator.previous();
                  if (nums[index] <= nums[j]) {//左边<当前元素
                      iterator.remove();
                  }else {
                      break a;//如果遇到大的数，就可以停止了。
                  }
              }

              // 加入当前元素
              window.addLast(j);

              //结果：返回当前窗口的最大值，deque ,元素左边最大值,
              //数组比窗口大 情况1
              if (j >= k - 1) {//当。窗口>index 是开始赋值，第一个值。
                  result[j - k + 1] = nums[window.peek()];
              }
          }

          //数组比窗口小 情况2
          if (nums.length < k) {
              result[0] = nums[window.peek()];
          }
          return result;
      }

}
//leetcode submit region end(Prohibit modification and deletion)

}